Metric space

 ( Mathematical Analysis ) 

In fact, these three distances, while they have distinct properties, are similar in some ways. Informally, points that are close in one are close in the others, too. This observation can be quantified with the formula $$d\_\backslash infty(p,q)\; \backslash leq\; d\_2(p,q)\; \backslash leq\; d\_1(p,q)\; \backslash leq\; 2d\_\backslash infty(p,q),$$ which holds for every pair of points $p,\; q\; \backslash in\; \backslash R^2$.

A radically different distance can be defined by setting Using , $$d(p,q)\; =\; p\backslash ne$$ In this discrete metric, all distinct points are 1 unit apart: none of them are close to each other, and none of them are very far away from each other either. Intuitively, the discrete metric no longer remembers that the set is a plane, but treats it just as an undifferentiated set of points.

All of these metrics make sense on $\backslash R^n$ as well as $\backslash R^2$.

The idea of an abstract space with metric properties was addressed in 1906 by René Maurice Fréchet and the term metric space was coined by Felix Hausdorff in 1914.F. Hausdorff (1914) Grundzuge der MengenlehreMohamed A. Khamsi & William A. Kirk (2001) Introduction to Metric Spaces and Fixed Point Theory, page 14, John Wiley & Sons

Fréchet's work laid the foundation for understanding convergence, continuity, and other key concepts in non-geometric spaces. This allowed mathematicians to study functions and sequences in a broader and more flexible way. This was important for the growing field of functional analysis. Mathematicians like Hausdorff and Stefan Banach further refined and expanded the framework of metric spaces. Hausdorff introduced topological spaces as a generalization of metric spaces. Banach's work in functional analysis heavily relied on the metric structure. Over time, metric spaces became a central part of modern mathematics. They have influenced various fields including topology, geometry, and applied mathematics. Metric spaces continue to play a crucial role in the study of abstract mathematical concepts.

An open set is a set which is a neighborhood of all its points. It follows that the open balls form a base for a topology on . In other words, the open sets of are exactly the unions of open balls. As in any topology, are the complements of open sets. Sets may be both open and closed as well as neither open nor closed.

This topology does not carry all the information about the metric space. For example, the distances , , and defined above all induce the same topology on $\backslash R^2$, although they behave differently in many respects. Similarly, $\backslash R$ with the Euclidean metric and its subspace the interval with the induced metric are homeomorphism but have very different metric properties.

Conversely, not every topological space can be given a metric. Topological spaces which are compatible with a metric are called metrizable space and are particularly well-behaved in many ways: in particular, they are paracompactRudin, Mary Ellen. A new proof that metric spaces are paracompact . Proceedings of the American Mathematical Society, Vol. 20, No. 2. (Feb., 1969), p. 603. (hence normal space) and first-countable. The Nagata–Smirnov metrization theorem gives a characterization of metrizability in terms of other topological properties, without reference to metrics.

A sequence converges to a point if for every there is an integer such that for all , .

A sequence converges to a point if for every open set containing there is an integer such that for all , $x\_n\; \backslash in\; U$.

To make this precise: a sequence in a metric space is Cauchy sequence if for every there is an integer such that for all , . By the triangle inequality, any convergent sequence is Cauchy: if and are both less than away from the limit, then they are less than away from each other. If the converse is true—every Cauchy sequence in converges—then is complete.

Euclidean spaces are complete, as is $\backslash R^2$ with the other metrics described above. Two examples of spaces which are not complete are and the rationals, each with the metric induced from $\backslash R$. One can think of as "missing" its endpoints 0 and 1. The rationals are missing all the irrationals, since any irrational has a sequence of rationals converging to it in $\backslash R$ (for example, its successive decimal approximations). These examples show that completeness is not a topological property, since $\backslash R$ is complete but the homeomorphic space is not.

This notion of "missing points" can be made precise. In fact, every metric space has a unique completion, which is a complete space that contains the given space as a dense set subset. For example, is the completion of , and the real numbers are the completion of the rationals.

Since complete spaces are generally easier to work with, completions are important throughout mathematics. For example, in abstract algebra, the p-adic numbers are defined as the completion of the rationals under a different metric. Completion is particularly common as a tool in functional analysis. Often one has a set of nice functions and a way of measuring distances between them. Taking the completion of this metric space gives a new set of functions which may be less nice, but nevertheless useful because they behave similarly to the original nice functions in important ways. For example, to differential equations typically live in a completion (a Sobolev space) rather than the original space of nice functions for which the differential equation actually makes sense.

The space is called precompact or totally bounded if for every there is a finite cover of by open balls of radius . Every totally bounded space is bounded. To see this, start with a finite cover by -balls for some arbitrary . Since the subset of consisting of the centers of these balls is finite, it has finite diameter, say . By the triangle inequality, the diameter of the whole space is at most . The converse does not hold: an example of a metric space that is bounded but not totally bounded is $\backslash R^2$ (or any other infinite set) with the discrete metric.

1. A metric space is compact if every open cover has a finite subcover (the usual topological definition).
2. A metric space is compact if every sequence has a convergent subsequence. (For general topological spaces this is called sequential compactness and is not equivalent to compactness.)
3. A metric space is compact if it is complete and totally bounded. (This definition is written in terms of metric properties and does not make sense for a general topological space, but it is nevertheless topologically invariant since it is equivalent to compactness.)

Compactness is important for similar reasons to completeness: it makes it easy to find limits. Another important tool is Lebesgue's number lemma, which shows that for any open cover of a compact space, every point is relatively deep inside one of the sets of the cover.

A function $f:M\_1\; \backslash to\; M\_2$ is distance-preserving if for every pair of points and in , $$d\_2(f(x),f(y))=d\_1(x,y).$$

If there is an isometry between the spaces and , they are said to be isometric. Metric spaces that are isometric are isomorphism.

• Topological definition. A function $f\backslash ,\backslash colon\; M\_1\backslash to\; M\_2$ is continuous if for every open set in , the preimage $f^\{-1\}(U)$ is open.
• Sequential continuity. A function $f\backslash ,\backslash colon\; M\_1\backslash to\; M\_2$ is continuous if whenever a sequence converges to a point in , the sequence $f(x\_1),f(x\_2),\backslash ldots$ converges to the point in .

(These first two definitions are not equivalent for all topological spaces.)

• ε–δ definition. A function $f\backslash ,\backslash colon\; M\_1\backslash to\; M\_2$ is continuous if for every point in and every there exists such that for all in we have

The only difference between this definition and the ε–δ definition of continuity is the order of quantifiers: the choice of δ must depend only on ε and not on the point . However, this subtle change makes a big difference. For example, uniformly continuous maps take Cauchy sequences in to Cauchy sequences in . In other words, uniform continuity preserves some metric properties which are not purely topological.

On the other hand, the Heine–Cantor theorem states that if is compact, then every continuous map is uniformly continuous. In other words, uniform continuity cannot distinguish any non-topological features of compact metric spaces.

A 1-Lipschitz map is sometimes called a nonexpanding or metric map. Metric maps are commonly taken to be the morphisms of the category of metric spaces.

A -Lipschitz map for is called a contraction. The Banach fixed-point theorem states that if is a complete metric space, then every contraction $f:M\; \backslash to\; M$ admits a unique fixed point. If the metric space is compact, the result holds for a slightly weaker condition on : a map $f:M\; \backslash to\; M$ admits a unique fixed point if

Formally, the map $f\backslash ,\backslash colon\; M\_1\backslash to\; M\_2$ is a quasi-isometric embedding if there exist constants and such that $$\backslash frac\{1\}\{A\}\; d\_2(f(x),f(y))-B\backslash leq\; d\_1(x,y)\backslash leq\; A\; d\_2(f(x),f(y))+B\; \backslash quad\backslash text\{\; for\; all\; \}\backslash quad\; x,y\backslash in\; M\_1.$$ It is a quasi-isometry if in addition it is quasi-surjective, i.e. there is a constant such that every point in $M\_2$ is at distance at most from some point in the image $f(M\_1)$.

• They are called homeomorphic (topologically isomorphic) if there is a homeomorphism between them (i.e., a continuous bijection with a continuous inverse). If $M\_1=M\_2$ and the identity map is a homeomorphism, then $d\_1$ and $d\_2$ are said to be topologically equivalent.
• They are called uniformic (uniformly isomorphic) if there is a uniform isomorphism between them (i.e., a uniformly continuous bijection with a uniformly continuous inverse).
• They are called bilipschitz homeomorphic if there is a bilipschitz bijection between them (i.e., a Lipschitz bijection with a Lipschitz inverse).
• They are called isometric if there is a (bijective) isometry between them. In this case, the two metric spaces are essentially identical.
• They are called quasi-isometric if there is a quasi-isometry between them.

• translation invariant: $d(x,y)\; =\; d(x+a,y+a)$ for every , , and in ; and
• : $d(\backslash alpha\; x,\; \backslash alpha\; y)\; =$

Among examples of metrics induced by a norm are the metrics , , and on $\backslash R^2$, which are induced by the Manhattan norm, the Euclidean norm, and the maximum norm, respectively. More generally, the Kuratowski embedding allows one to see any metric space as a subspace of a normed vector space.

Infinite-dimensional normed vector spaces, particularly spaces of functions, are studied in functional analysis. Completeness is particularly important in this context: a complete normed vector space is known as a Banach space. An unusual property of normed vector spaces is that linear transformations between them are continuous if and only if they are Lipschitz. Such transformations are known as .

A geodesic metric space is a metric space which admits a geodesic between any two of its points. The spaces $(\backslash R^2,d\_1)$ and $(\backslash R^2,d\_2)$ are both geodesic metric spaces. In $(\backslash R^2,d\_2)$, geodesics are unique, but in $(\backslash R^2,d\_1)$, there are often infinitely many geodesics between two points, as shown in the figure at the top of the article.

The space is a length space (or the metric is intrinsic) if the distance between any two points and is the infimum of lengths of paths between them. Unlike in a geodesic metric space, the infimum does not have to be attained. An example of a length space which is not geodesic is the Euclidean plane minus the origin: the points and can be joined by paths of length arbitrarily close to 2, but not by a path of length 2. An example of a metric space which is not a length space is given by the straight-line metric on the sphere: the straight line between two points through the center of the Earth is shorter than any path along the surface.

Given any metric space , one can define a new, intrinsic distance function on by setting the distance between points and to be the infimum of the -lengths of paths between them. For instance, if is the straight-line distance on the sphere, then is the great-circle distance. However, in some cases may have infinite values. For example, if is the Koch snowflake with the subspace metric induced from $\backslash R^2$, then the resulting intrinsic distance is infinite for any pair of distinct points.

The Riemannian metric is uniquely determined by the distance function; this means that in principle, all information about a Riemannian manifold can be recovered from its distance function. One direction in metric geometry is finding purely metric ("synthetic") formulations of properties of Riemannian manifolds. For example, a Riemannian manifold is a space (a synthetic condition which depends purely on the metric) if and only if its sectional curvature is bounded above by . Thus spaces generalize upper curvature bounds to general metric spaces.

One application of metric measure spaces is generalizing the notion of Ricci curvature beyond Riemannian manifolds. Just as and generalize sectional curvature bounds, are a class of metric measure spaces which generalize lower bounds on Ricci curvature.

For any undirected connected graph , the set of vertices of can be turned into a metric space by defining the distance between vertices and to be the length of the shortest edge path connecting them. This is also called shortest-path distance or geodesic distance. In geometric group theory this construction is applied to the Cayley graph of a (typically infinite) finitely-generated group, yielding the word metric. Up to a bilipschitz homeomorphism, the word metric depends only on the group and not on the chosen finite generating set.

A significant result in this area is that any finite metric space can be probabilistically embedded into a tree metric with an expected distortion of $O(log\; n)$, where $n$ is the number of points in the metric space.

This embedding is notable because it achieves the best possible asymptotic bound on distortion, matching the lower bound of $\backslash Omega(log\; n)$. The tree metrics produced in this embedding dominate the original metrics, meaning that distances in the tree are greater than or equal to those in the original space. This property is particularly useful for designing approximation algorithms, as it allows for the preservation of distance-related properties while simplifying the underlying structure.

The result has significant implications for various computational problems:

• Network design: Improves approximation algorithms for problems like the Group Steiner tree problem (a generalization of the Steiner tree problem) and Buy-at-bulk network design (a problem in Network planning and design) by simplifying the metric space to a tree metric.
• Clustering: Enhances algorithms for clustering problems where hierarchical clustering can be performed more efficiently on tree metrics.
• Online algorithms: Benefits problems like the k-server problem and metrical task system by providing better competitive ratios through simplified metrics.

The technique involves constructing a hierarchical decomposition of the original metric space and converting it into a tree metric via a randomized algorithm. The $O(log\; n)$ distortion bound has led to improved approximation ratios in several algorithmic problems, demonstrating the practical significance of this theoretical result.

• Functions to a metric space. If is any set and is a metric space, then the set of all $f\; \backslash colon\; X\; \backslash to\; M$ (i.e. those functions whose image is a bounded subset of $M$) can be turned into a metric space by defining the distance between two bounded functions and to be $$d(f,g)\; =\; \backslash sup\_\{x\; \backslash in\; X\}\; d(f(x),g(x)).$$ This metric is called the uniform metric or supremum metric. If is complete, then this function space is complete as well; moreover, if is also a topological space, then the subspace consisting of all bounded continuous functions from to is also complete. When is a subspace of $\backslash R^n$, this function space is known as a classical Wiener space.
• and . There are many ways of measuring distances between strings of characters, which may represent sentences in computational linguistics or code words in coding theory. Edit distances attempt to measure the number of changes necessary to get from one string to another. For example, the Hamming distance measures the minimal number of substitutions needed, while the Levenshtein distance measures the minimal number of deletions, insertions, and substitutions; both of these can be thought of as distances in an appropriate graph.
• Graph edit distance is a measure of dissimilarity between two graphs, defined as the minimal number of Graph operations required to transform one graph into another.
• Wasserstein metrics measure the distance between two measures on the same metric space. The Wasserstein distance between two measures is, roughly speaking, the cost of transporting one to the other.
• The set of all by matrices over some field is a metric space with respect to the rank distance $d(A,B)\; =\; \backslash mathrm\{rank\}(B\; -\; A)$.
• The Helly metric in game theory measures the difference between strategies in a game.

Suppose is a metric space, and let be a subset of . The distance from to a point of is, informally, the distance from to the closest point of . However, since there may not be a single closest point, it is defined via an infimum: $$d(x,S)\; =\; \backslash inf\backslash \{d(x,s)\; :\; s\; \backslash in\; S\; \backslash \}.$$ In particular, $d(x,\; S)=0$ if and only if belongs to the closure of . Furthermore, distances between points and sets satisfy a version of the triangle inequality: $$d(x,S)\; \backslash leq\; d(x,y)\; +\; d(y,S),$$ and therefore the map $d\_S:M\; \backslash to\; \backslash R$ defined by $d\_S(x)=d(x,S)$ is continuous. Incidentally, this shows that metric spaces are completely regular.

Given two subsets and of , their Hausdorff distance is $$d\_H(S,T)\; =\; \backslash max\; \backslash \{\; \backslash sup\backslash \{d(s,T)\; :\; s\; \backslash in\; S\; \backslash \}\; ,\; \backslash sup\backslash \{\; d(t,S)\; :\; t\; \backslash in\; T\; \backslash \}\; \backslash \}.$$ Informally, two sets and are close to each other in the Hausdorff distance if no element of is too far from and vice versa. For example, if is an open set in Euclidean space is an Delone set inside , then . In general, the Hausdorff distance $d\_H(S,T)$ can be infinite or zero. However, the Hausdorff distance between two distinct compact sets is always positive and finite. Thus the Hausdorff distance defines a metric on the set of compact subsets of .

The Gromov–Hausdorff metric defines a distance between (isometry classes of) compact metric spaces. The Gromov–Hausdorff distance between compact spaces and is the infimum of the Hausdorff distance over all metric spaces that contain and as subspaces. While the exact value of the Gromov–Hausdorff distance is rarely useful to know, the resulting topology has found many applications.

• Given a metric space and an increasing concave function $f\; \backslash colon\; [0,\backslash infty)\; \backslash to\; [0,\backslash infty)$ such that if and only if , then $d\_f(x,y)=f(d(x,y))$ is also a metric on . If for some real number , such a metric is known as a snowflake of .
• The tight span of a metric space is another metric space which can be thought of as an abstract version of the convex hull.
• The knight's move metric, the minimal number of knight's moves to reach one point in $\backslash mathbb\{Z\}^2$ from another, is a metric on $\backslash mathbb\{Z\}^2$.
• The British Rail metric (also called the "post office metric" or the "French railway metric") on a normed vector space is given by $d(x,y)\; =\; \backslash lVert\; x\; \backslash rVert\; +\; \backslash lVert\; y\; \backslash rVert$ for distinct points $x$ and $y$, and $d(x,x)\; =\; 0$. More generally $\backslash lVert\; \backslash cdot\; \backslash rVert$ can be replaced with a function $f$ taking an arbitrary set $S$ to non-negative reals and taking the value $0$ at most once: then the metric is defined on $S$ by $d(x,y)\; =\; f(x)\; +\; f(y)$ for distinct points $x$ and $y$, and The name alludes to the tendency of railway journeys to proceed via London (or Paris) irrespective of their final destination.
• The Robinson–Foulds metric used for calculating the distances between Phylogenetic trees in Phylogenetics

Similarly, a metric on the topological product of countably many metric spaces can be obtained using the metric $$d(x,y)=\backslash sum\_\{i=1\}^\backslash infty\; \backslash frac1\{2^i\}\backslash frac\{d\_i(x\_i,y\_i)\}\{1+d\_i(x\_i,y\_i)\}.$$

The topological product of uncountably many metric spaces need not be metrizable. For example, an uncountable product of copies of $\backslash mathbb\{R\}$ is not first-countable and thus is not metrizable.

The quotient metric $d\text{'}$ is characterized by the following universal property. If $f\backslash ,\backslash colon(M,d)\backslash to(X,\backslash delta)$ is a metric (i.e. 1-Lipschitz) map between metric spaces satisfying whenever $x\; \backslash sim\; y$, then the induced function $\backslash overline\{f\}\backslash ,\backslash colon\; \{M/\backslash sim\}\backslash to\; X$, given by $\backslash overline\{f\}(x)=f(x)$, is a metric map $\backslash overline\{f\}\backslash ,\backslash colon\; (M/\backslash sim,d\text{'})\backslash to\; (X,\backslash delta).$

The quotient metric does not always induce the quotient topology. For example, the topological quotient of the metric space $\backslash N\; \backslash times\; 0,1$ identifying all points of the form $(n,\; 0)$ is not metrizable since it is not first-countable, but the quotient metric is a well-defined metric on the same set which induces a coarser topology. Moreover, different metrics on the original topological space (a disjoint union of countably many intervals) lead to different topologies on the quotient.See , although in this book the quotient $\backslash N\; \backslash times\; 0,1/\backslash N\; \backslash times\; \backslash \{0\backslash \}$ is incorrectly claimed to be homeomorphic to the topological quotient.

A topological space is sequential space if and only if it is a (topological) quotient of a metric space.Goreham, Anthony. Sequential convergence in Topological Spaces . Honours' Dissertation, Queen's College, Oxford (April, 2001), p. 14

• are spaces in which distances are not defined, but uniform continuity is.
• are spaces in which point-to-set distances are defined, instead of point-to-point distances. They have particularly good properties from the point of view of category theory.
• are a generalization of metric spaces and that can be used to unify the notions of metric spaces and Domain theory.

There are also numerous ways of relaxing the axioms for a metric, giving rise to various notions of generalized metric spaces. These generalizations can also be combined. The terminology used to describe them is not completely standardized. Most notably, in functional analysis pseudometrics often come from on vector spaces, and so it is natural to call them "semimetrics". This conflicts with the use of the term in topology.

• , yielding the notion of a generalised metric.
• More general . In the absence of an addition operation, the triangle inequality does not make sense and is replaced with an ultrametric inequality. This leads to the notion of a generalized ultrametric.

1. $d(x,\; y)\; \backslash geq\; 0$
2. $d(x,x)=0$
3. $d(x,y)=d(y,x)$
4. $d(x,z)\backslash leq\; d(x,y)\; +\; d(y,z)$.

In some contexts, pseudometrics are referred to as semimetrics because of their relation to .

1. $d(x,\; y)\; \backslash geq\; 0$
2. $d(x,y)=0\; \backslash iff\; x=y$
3. $d(x,z)\; \backslash leq\; d(x,y)\; +\; d(y,z)$

Quasimetrics are common in real life. For example, given a set of mountain villages, the typical walking times between elements of form a quasimetric because travel uphill takes longer than travel downhill. Another example is the taxicab geometry in a city with one-way streets: here, a shortest path from point to point goes along a different set of streets than a shortest path from to and may have a different length.

A quasimetric on the reals can be defined by setting The 1 may be replaced, for example, by infinity or by $1\; +\; \backslash sqrt\{y-x\}$ or any other subadditivity function of . This quasimetric describes the cost of modifying a metal stick: it is easy to reduce its size by filing it down, but it is difficult or impossible to grow it.

Given a quasimetric on , one can define an -ball around to be the set $\backslash \{y\; \backslash in\; X$

1. $d(x,y)\backslash geq\; 0$
2. $d(x,y)=0\; \backslash implies\; x=y$
3. $d(x,y)=d(y,x)$
4. $d(x,z)\backslash leq\; d(x,y)+d(y,z).$

Metametrics appear in the study of Gromov hyperbolic metric spaces and their boundaries. The visual metametric on such a space satisfies $d(x,x)=0$ for points $x$ on the boundary, but otherwise $d(x,x)$ is approximately the distance from $x$ to the boundary. Metametrics were first defined by Jussi Väisälä. In other work, a function satisfying these axioms is called a partial metric or a dislocated metric.

1. $d(x,y)\backslash geq\; 0$
2. $d(x,y)=0\; \backslash iff\; x=y$
3. $d(x,y)=d(y,x)$

Some authors work with a weaker form of the triangle inequality, such as:

{